COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macros[pap,rpg]
C00008 ENDMK
C⊗;
\input macros[pap,rpg]
\magnification\magstep1

\paper:Outline proposal for Stanford Hep and parallel Lisp.

	It is generally agreed that the main hope for large increases
in computer speed, whether for numerical work or artificial
intelligence, lies in massive parallelism.  Projects are being undertaken
that will involve hundreds or even thousands of processors.
However, no-one has yet demonstrated the ability to make general purpose
use of even two processors on symbolic computation for a single problem.

	We, Richard Gabriel and John McCarthy, have a variant of Lisp
called Qlambda, described in our paper (Gabriel and McCarthy 1984),
which we believe will allow Lisp to effectively use many processors.
It is based on the following ideas:

\numitem{1.}The programmer can tell when a computation will allow
parallelism and can indicate this by using appropriate constructs
in the source language.  In our case these are called QLET and QLAMBDA.

\numitem{2.}When tasks that may be done in parallel are found they are
placed on a queue.  Free processors take tasks from the queue.
The source and compiled programs do not require any specific number
of processes.

\numitem{3.}It is important to control the amount of multi-processing
and limit it to not much more than the number of processors available.
This is because handling the multi-processing involves computational
overhead, and if allowed to occur at a low level, this overhead could
swamp the useful computation.  The control is accomplished in Qlambda
by runtime parameters to QLET and QLAMBDA that determine whether
parallelism is actually to be allowed.

	We believe this simple scheme will work for effective Lisp
multi-processing in AI and symbolic mathematics applications.  Our
paper includes simulations that indicate that this is true.

	We propose to acquire a Hep, develop Qlambda, and test it
on applications that will provide a good test of how much
speed gain can be obtained from multi-processing using the features
of Hep which include a certain amount of data-flow architecture.
The results should help DARPA guide its more ambitious multi-processing
efforts by determining what additional architectural features are important
for multi-processing in Lisp.

	Besides implementing Qlambda, we propose to implement Macsyma
and some large Macsyma applications.  Implementing Macsyma and Macsyma
applications has the advantage of providing a very large and varied collection
of Lisp functions each of which is computationally expensive.
Making them run in parallel is a well-defined task that will nevertheless
fully test Qlambda and the Hep.

	Besides this, HPP has proposed some major AI applications that they will
program in Qlambda and test on simulators; if Qlambda were to exist on
the Hep, they would mount the applications on it.

	Acquiring and operating a Hep will be expensive in terms of
acquisition cost, space (Welch Road where HPP is located), and personnel.
Substantial personnel will be required for the Macsyma and symbolic
computation projects.  Nevertheless, we believe that this project
provides and opportunity to get a preview of how to solve the problems
that will be faced by the much more expensive parallel processor
projects now being undertaken.

	If there is sufficient interest a detailed proposal with costs
will be prepared.

\bye